//
// Created by id on 2025/10/6.
//  @file myCharString.c
//  @desc 基于固定数组实现的简单字符串类型 myChar，支持基本操作：
//        判空、判满、长度、比较、复制、子串、拼接、匹配、清空。
//  @author id
//  @date 2025-10-06
//  @version 1.0
//

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ------------------------- 常量定义 -------------------------

#define MAX_SIZE 100  ///< myChar 最大容量

// ------------------------- 类型定义 -------------------------

/**
 * @struct myChar
 * @brief 自定义字符串类型
 *
 * - ch[MAX_SIZE] : 存储字符数组
 * - length       : 当前字符串长度
 */
typedef struct myChar {
    char ch[MAX_SIZE];  ///< 字符数组
    int length;         ///< 当前长度
} myChar;

// ------------------------- 基本操作 -------------------------

/**
 * @brief 判断字符串是否已满
 * @param c 指向 myChar 对象
 * @return true 表示已满，false 表示未满
 */
bool isFull(myChar *c) {
    return c->length == MAX_SIZE;
}

/**
 * @brief 判断字符串是否为空
 * @param c 指向 myChar 对象
 * @return true 表示空字符串，false 表示非空
 */
bool isEmpty(myChar *c) {
    return c->length == 0;
}

/**
 * @brief 获取字符串长度
 * @param c 指向 myChar 对象
 * @return 返回字符串长度
 */
int strLength(myChar *c) {
    return c->length;
}

/**
 * @brief 字符串比较
 * @param a 指向第一个 myChar 对象
 * @param b 指向第二个 myChar 对象
 * @return
 *    - >0 : a 大于 b
 *    - 0  : a 等于 b
 *    - <0 : a 小于 b
 * @note 类似标准 strcmp，先逐字符比较，若完全相同则长度决定大小
 */
int strCompare(myChar *a, myChar *b) {
    int min_len = a->length < b->length ? a->length : b->length;
    for (int i = 0; i < min_len; i++) {
        if (a->ch[i] != b->ch[i]) {
            return a->ch[i] - b->ch[i];
        }
    }
    return a->length - b->length;
}

/**
 * @brief 将字符串 a 复制到 b
 * @param a 源字符串
 * @param b 目标字符串
 * @return true 表示复制成功，false 表示长度超出最大容量
 * @note 复制后 b 的原数据全部被覆盖
 */
bool strCopy(myChar *a, myChar *b) {
    int lenA = a->length;

    if (lenA > MAX_SIZE) {  // 源字符串超过容量
        return false;
    }

    for (int i = 0; i < lenA; i++) {
        b->ch[i] = a->ch[i];
    }
    b->length = a->length;
    return true;
}

/**
 * @brief 获取源字符串的子串
 * @param subChar 输出子串
 * @param src 源字符串
 * @param pos 起始位置（从0开始）
 * @param len 子串长度
 * @note 如果 pos 超出范围，函数会输出错误信息。
 *       如果 pos+len 超出 src 长度，会自动截断。
 */
void subString(myChar *subChar, myChar *src, int pos, int len) {
    if (isEmpty(src)) {
        printf("char is empty\n");
        return;
    }

    if (pos < 0 || pos >= src->length) {
        printf("pos is out of range\n");
        return;
    }

    if (pos + len > src->length) {
        len = src->length - pos;  // 截断
    }

    for (int i = 0; i < len; i++) {
        subChar->ch[i] = src->ch[pos + i];
    }

    subChar->length = len;
}

/**
 * @brief 拼接字符串 b 到 a 的末尾
 * @param a 目标字符串，同时也是拼接后的结果
 * @param b 要拼接的字符串
 * @note 如果拼接后长度超过 MAX_SIZE，则函数直接返回，不做拼接
 */
void concat(myChar *a, myChar *b) {
    int back_len = a->length;

    if (a->length + b->length > MAX_SIZE) {
        return;  // 超出容量，忽略操作
    }

    for (int i = 0; i < b->length; i++) {
        a->ch[back_len + i] = b->ch[i];
    }
    a->length += b->length;
}

/**
 * @brief 在主串 text 中查找子串 pattern 的首次出现位置（朴素匹配算法）
 * @param text 主串（被搜索的字符串）
 * @param pattern 模式串（要匹配的子串）
 * @return
 *   - 返回值 >= 0 ：表示匹配成功的位置（从 0 开始计数）
 *   - 返回值 = -1 ：表示未匹配到或参数无效
 * @note
 *   - 实际应用中推荐使用此版本，索引从0开始，更符合 C 语言数组习惯
 *   - 该函数实现的是最基础的字符串匹配算法（Brute Force / BF 算法）采用了 0-based 索引
 *   - 算法思想：主串从左向右逐字符匹配，若不匹配则回溯到上次匹配起点的下一个字符。
 *   - 时间复杂度：O(n * m)，其中 n 为主串长度，m 为子串长度。
 */
int indexBase0(myChar *text, myChar *pattern) {
    if (text->length == 0 || pattern->length == 0 || pattern == NULL || text == NULL) {
        printf("the length is 0\n");
        return -1;
    }

    if (pattern->length > text->length) {
        printf("the length is greater than length\n");
        return -1;
    }

    int i = 0;  // 主串指针
    int j = 0;  // 子串指针

    while (i < text->length && j < pattern->length) {
        if (text->ch[i] == pattern->ch[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;  // 主串回退
            j = 0;          // 子串重头匹配
        }
    }

    if (j == pattern->length) {
        return i - pattern->length;
    } else {
        return -1;
    }
}

/**
 * @brief 在主串 text 中查找模式串 pattern 的首次出现位置（普通 BF 算法）
 * @param text 主串（被匹配的字符串）
 * @param pattern 模式串（待查找的字符串）
 * @return
 *   - 返回值 >= 1 ：匹配成功的位置（1-based 下标）
 *   - 返回值 = -1 ：未匹配到或输入无效
 * @note
 *   - 纯教学版本，保留教材 BF 算法逻辑
 *   - 时间复杂度：O(n * m)，n 为主串长度，m 为模式串长度
 */
int indexBase1(myChar *text, myChar *pattern) {
    if (text->length == 0 || pattern->length == 0 || pattern == NULL || text == NULL) {
        printf("the length is 0\n");
        return -1;
    }
    if (pattern->length > text->length) {
        printf("pattern length is greater than text length\n");
        return -1;
    }

    int i = 1;  // 主串指针（1-based）
    int j = 1;  // 模式串指针（1-based）

    while (i <= text->length && j <= pattern->length) {
        if (text->ch[i] == pattern->ch[j]) {
            i++;
            j++;
        } else {
            i = i - j + 2;  // 回退主串指针到下一个起始位置
            j = 1;          // 模式串指针重置
        }
    }

    if (j > pattern->length) { // 因为在循环里面 j的值被多加的一次。
                               // 所以不使用 j== parttern->length
        return i - pattern->length;  // 返回主串匹配起始位置
    } else {
        return -1;  // 未匹配到
    }
}


/**
 * @brief 清空字符串内容（相当于销毁操作）
 * @param c 指向 myChar 对象
 * @note
 *   - 由于 myChar 使用静态数组存储，不存在动态内存分配；
 *   - 清空后长度设为 0，并以 '\0' 作为结束标志
 */
void clear(myChar *c) {
    c->length = 0;
    c->ch[0] = '\0';
    printf("clear and destroy success!\n");
}

// ------------------------- 测试主函数 -------------------------

int main() {
    // 初始化字符串
    myChar s1 = {"Hello1111", 10};
    myChar s2 = {"Hello", 5};

    // 字符串匹配（0-based）
    int matchIndex0 = indexBase0(&s1, &s2);
    if (matchIndex0 == -1) {
        printf("Does not match\n");
    } else {
        printf("Match index (0-based): %d\n", matchIndex0);
    }
    printf("-----------------\n");

    // 另一组字符串（手动赋值）
    myChar text2, pattern2;

    text2.length = 6;
    text2.ch[1] = 'a';
    text2.ch[2] = 'b';
    text2.ch[3] = 'c';
    text2.ch[4] = 'd';
    text2.ch[5] = 'e';
    text2.ch[6] = 'f';

    pattern2.length = 3;
    pattern2.ch[1] = 'c';
    pattern2.ch[2] = 'd';
    pattern2.ch[3] = 'e';

    // 字符串匹配（1-based）
    int matchIndex1 = indexBase1(&text2, &pattern2);
    if (matchIndex1 == -1) {
        printf("Does not match\n");
    } else {
        printf("Match index (1-based): %d\n", matchIndex1);
    }

    // 字符串复制
    if (strCopy(&s1, &s2)) {
        printf("copy success: ");
        for (int i = 0; i < s2.length; i++) {
            printf("%c", s2.ch[i]);
        }
        printf("\n");
    } else {
        printf("copy fail\n");
    }

    // 字符串比较
    int result = strCompare(&s1, &s2);
    printf("result = %d\n", result);

    // 获取子串
    myChar subChar;
    subString(&subChar, &s1, 4, 4);
    for (int i = 0; i < subChar.length; i++) {
        printf("%c", subChar.ch[i]);
    }
    printf("\n");

    printf("========================\n");

    // 拼接字符串
    concat(&s1, &s2);
    for (int i = 0; i < s1.length; i++) {
        printf("%c", s1.ch[i]);
    }
    printf("\n");

    // 清理字符数组
    clear(&s1);
    return 0;
}
